package basic.basic_class04;

public class Test {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    //计算完全二叉树中节点的个数
    public static int findNodeTotal(Node root){
        if(root == null) return 0;
        int res = 0;
        // 首先计算出树的总高度
        int h1 = findHeight(root);
        // 计算出右子树的高度
        int h2 = findHeight(root.left);
        // 决策条件
        if(h1 == h2 + 1){
            // 宝石左侧子树为满二叉树
            res += (1 << (h1 - 1)) + findNodeTotal(root.right);
        }else{
            res =+ findNodeTotal(root.left) + (1 << h2);
        }
        return res;
    }

    // 计算当前二叉树的深度
    public static int findHeight(Node root){
        if(root == null) return 0;
        int res = 1;
        Node cur = root;
        while(cur.left != null){
            res++;
            cur = cur.left;
        }
        return res;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        System.out.println(findNodeTotal(head));
    }
}